package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/16 9:49
 */
public class C121 {


    // https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
    // 暴力解: 从我开始找都后边的最小值, 记录答案. 每一步都找, O(n^2)超出时间限制
    public static int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] > prices[i]) {
                    ans = Math.max(ans, (prices[j] - prices[i]));
                }
            }
        }
        return ans;
    }

    // 窗口解: 找到不回退的思路.
    // 如果遇到比我小的, 就先不走, 先把L区域走完
    // 否则能往右走就往右走
    public static int maxProfit2(int[] prices) {
        int L = 0, R = 0, ans = 0;
        while (R < prices.length) {
            if (R + 1 < prices.length && prices[R + 1] >= prices[L]) {
                R++;
                ans = Math.max(ans, prices[R] - prices[L]);
            } else {
                // 不比我大了, 左边一直往右扩, 收集答案
                while (L < R) {
                    L++;
                    ans = Math.max(ans, prices[R] - prices[L]);
                }
                // L == R
                L++; R++;
            }
        }
        return ans;
    }

    // 就是一个很简单的解: 非得搞的那么麻烦.
    public static int maxProfit3(int[] prices) {
        int min = prices[0], max = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(prices[i], min);
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }

    // for test
    public static void main(String[] args) {
        int[] price = {7,1,5,3,6,4,5321,43,554,321,685,13,1,324,165321,532,16,321,32,132,123,1056321,56,16,53,1231,32,132,1,23,132,123,1,231,32};
        System.out.println(maxProfit(price));
        System.out.println(maxProfit2(price));
        System.out.println(maxProfit3(price));
    }
}
